package org.coone.veteran.basic.array;

import java.util.ArrayList;
import java.util.List;

public class ArrayUtils {

	/**
	 * 给定两个数组xArray、yArray（均为升序整数数组，数组内元素不重复），找出仅存在于xArray中的所有元素，并以数组格式返回
	 * 
	 * <pre>
	 *     举例：xArray为{-1,0,1,2,3,4,6,8,10} yArray为{2,3,5,6,9}，那么输出应为：{-1,0,1,4,8,10}
	 * </pre>
	 * 
	 * @param xArray
	 * @param yArray
	 * @return
	 */
	public static int[] findDiffBetweenArray(int[] xArray, int[] yArray) {
		int xHeaderCursor = 0, xTailerCursor = xArray.length - 1;
		int yHeaderCursor = 0, yTailerCursor = yArray.length - 1;

		// 无交集
		if (0 == xArray.length) {
			return new int[0];
		}
		if (0 == yArray.length || xArray[xHeaderCursor] > yArray[yTailerCursor]
				|| xArray[xTailerCursor] < yArray[yHeaderCursor]) {
			return xArray;
		}

		int[] headerResult = new int[xArray.length], tailerResult = new int[xArray.length];
		int headerIndex = xHeaderCursor, tailerIndex = xTailerCursor;

		// （核心处理）有交集，则对xArray采用头尾双向收集不同元素的方式处理
		int yHeaderItem = yArray[yHeaderCursor], yTailerItem = yArray[yTailerCursor];
		while (yHeaderCursor <= yTailerCursor && xHeaderCursor <= xTailerCursor) {
			// 从xArray头部开始收集不同元素
			while (yHeaderItem >= xArray[xHeaderCursor]) {
				if (yHeaderItem == xArray[xHeaderCursor]) {
					++xHeaderCursor;
					break;
				}
				headerResult[headerIndex++] = xArray[xHeaderCursor++];
			}

			// 从xArray尾部开始收集不同元素
			while (yTailerItem <= xArray[xTailerCursor]) {
				if (yTailerItem == xArray[xTailerCursor]) {
					--xTailerCursor;
					break;
				}
				tailerResult[tailerIndex--] = xArray[xTailerCursor--];
			}

			// 从yArray头部与尾部同时跳过已处理元素
			yHeaderItem = yArray[++yHeaderCursor];
			yTailerItem = yArray[--yTailerCursor];
		}

		// 当yArray缩进完成之后，xArray还有剩余元素，则收集剩余元素
		while (xHeaderCursor <= xTailerCursor) {
			headerResult[headerIndex++] = xArray[xHeaderCursor++];
		}

		int[] result = new int[headerIndex + (xArray.length - tailerIndex - 1)];
		System.arraycopy(headerResult, 0, result, 0, headerIndex);
		System.arraycopy(tailerResult, tailerIndex + 1, result, headerIndex,
				xArray.length - tailerIndex - 1);
		
		return result;
	}

	public static int[] findDiffBetweenArray2(int[] xArray, int[] yArray) {
		List<Integer> z = new ArrayList<Integer>();
		int i = 0, j = 0;
		while (i < xArray.length) {
			if (j >= yArray.length) {
				z.add(xArray[i]);
				i++;
				continue;
			}
			//
			if (xArray[i] > yArray[j]) {
				j++;
			} else if (xArray[i] == yArray[j]) {
				i++;
			} else {
				z.add(xArray[i]);
				i++;
			}
		}
		//
		int[] r = new int[z.size()];
		for (int k = 0; k < z.size(); k++) {
			r[k] = z.get(k);
		}
		
		return r;
	}
	
	public static Integer[] findDiffBetweenArray3(int[] array1, int[] array2) {
        int array1Index = 0, array2Index = 0;
        List<Integer> result = new ArrayList<Integer>();
        while (array1Index < array1.length) {
            while (array2Index < array2.length && array1[array1Index] > array2[array2Index]) {
                array2Index++;
            }
            if (array2Index == array2.length) {
                for (int i = array1Index; i < array1.length; i++) {
                    result.add(array1[i]);
                }
                break;
            }
            else if (array1[array1Index] < array2[array2Index]) {
                result.add(array1[array1Index]);
            }
            else {
                array2Index++;
            }
            array1Index++;
        }
        return result.toArray(new Integer[result.size()]);
    }

	public static void main(String[] args) {
		int[] xArray = new int[] { -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
		int[] yArray = new int[] { 2, 4, 10, 11 };

		System.out.println("********************************************");
		long startTime = System.currentTimeMillis();
		System.out.println("startTime -> " + startTime);
		int[] diffArray1 = ArrayUtils.findDiffBetweenArray(xArray, yArray);
		long endTime = System.currentTimeMillis();
		System.out.println("endTime -> " + endTime);
		long excTime = endTime - startTime;
		System.out.println("excTime -> " + excTime);
		System.out.println("findDiffBetweenArray执行时间：" + excTime);

		System.out.println();
		for (int i = 0; i < diffArray1.length; i++) {
			System.out.printf("%s ", diffArray1[i]);
		}

		System.out.println();
		System.out.println("********************************************");
		long startTime1 = System.currentTimeMillis();
		System.out.println("startTime1 -> " + startTime1);
		Integer[] diffArray2 = ArrayUtils.findDiffBetweenArray3(xArray, yArray);
		long endTime1 = System.currentTimeMillis();
		System.out.println("endTime1 -> " + endTime1);
		long excTime1 = endTime1 - startTime1;
		System.out.println("excTime1 -> " + excTime1);
		System.out.println("findDiffBetweenArray2执行时间：" + excTime1);

		System.out.println();
		for (int i = 0; i < diffArray2.length; i++) {
			System.out.printf("%s ", diffArray2[i]);
		}

		System.out.println();
		System.out.println("********************************************");
	}

	public static void main2(String[] args) {
		for (int i = 0; i < 1234; i++) {
			System.out.printf("%s, ", i);
		}
	}
}
